#include<iostream>
#include<stack>
using namespace std;

struct Position
{
    int x;
    int y;
    Position(int i, int j)
    : x(i)
    , y(j)
    {
    }
};

const int mazeRow = 10;
const int mazeCol = 10;

char maze[mazeRow][mazeCol] = 
{
    {'#', '#', '#', '#', '#', '#', '#', '#', '#', '#'},
    {'#', ' ', ' ', '#', ' ', ' ', ' ', '#', ' ', '#'},
    {'#', ' ', ' ', '#', ' ', ' ', ' ', '#', ' ', '#'},
    {'#', ' ', ' ', ' ', ' ', '#', '#', ' ', ' ', '#'},
    {'#', ' ', '#', '#', '#', ' ', ' ', ' ', '#', '#'},
    {'#', ' ', ' ', ' ', '#', ' ', ' ', ' ', '#', '#'},
    {'#', ' ', '#', ' ', ' ', ' ', '#', ' ', ' ', '#'},
    {'#', '#', '#', '#', '#', ' ', '#', '#', ' ', '#'},
    {'#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', 'A', '#'},
    {'#', '#', '#', '#', '#', '#', '#', '#', '#', '#'}
};
bool bVisited[mazeRow][mazeCol] = {false};

bool IsValidPos(int i, int j)
{
    return maze[i][j] != '#' && !bVisited[i][j];
}

int main(void)
{
    
    for (int i = 0; i < mazeRow; ++i)
    {
        for (int j = 0; j < mazeCol; ++j)
        {
            cout<< maze[i][j]<< " ";
        }
        cout<<endl;
    }
    
    stack<Position> stkPath;
    stkPath.push(Position(1, 1));
    
    do
    {
        Position pos = stkPath.top();
        int x = pos.x;
        int y = pos.y;
        bool flag = true;
        
        if ('A' == maze[x][y])
        {
            break;
        }
        
        if (IsValidPos(x, y + 1))
        {
            y += 1;
        }
        else if (IsValidPos(x + 1, y))
        {
            x += 1;
        }
        else if (IsValidPos(x, y - 1))
        {
            y -= 1;
        }
        else if (IsValidPos(x - 1, y))
        {
            x -= 1;
        }
        else
        {
            flag = false;
        }
        
        if (flag)
        {
            stkPath.push(Position(x, y));
            bVisited[x][y] = true;
        }
        else
        {
            stkPath.pop();
        }
    }while (!stkPath.empty());
    
    if (stkPath.empty())
    {
        cout<< "No Path!\n";
    }
    else
    {
        while (!stkPath.empty())
        {
            Position pos = stkPath.top();
            maze[pos.x][pos.y] = '*';
            stkPath.pop();
        }
        
        for (int i = 0; i < mazeRow; ++i)
        {
            for (int j = 0; j < mazeCol; ++j)
            {
                cout<< maze[i][j]<< " ";
            }
            cout<<endl;
        }
    }
    
    system("pause");
}
